package graph_base_expression.adjacentMatrix;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author sijunqiang
 * @data 2021/6/6 14:44
 * @description: 邻接矩阵(邻接表的本质在计算机中其实就是一个二维数组)
 *
 * <p>功能：使用邻接矩阵--表示一个无向无权图<p>
 * 主要的函数是：
 * 1：使用二维数组建图
 * 2：获取一个顶点相邻的顶点列表。
 * 3：获取一个顶点的度。
 * 4：判断 两个点是否相邻
 */
public class AdjacentMatrix {

    // V-代表图的顶点的个数
    private int V;

    // E-代表图的边的个数
    private int E;

    // adj-代表是使用一个二维数组表示的图的数据
    private int[][] adj;


    /**
     * <使用邻接矩阵的形式-表示一个无向无权图>
     * 第一，先读取指定文件的数据
     * 第二，检验每个顶点的合法性(由于邻接矩阵表示的简单图 因此它不包括自环边和平行边)
     * 第三，依次遍历往二维数组中添加元素
     */
    public AdjacentMatrix(String filename) {
        //读取指定的文件
        File file = new File(filename);
        // 从文件中读取数据 这样写好处就是 不用关闭流资源了
        try (Scanner scanner = new Scanner(file)) {
            V = scanner.nextInt();
            if (V < 0) {
                throw new IllegalArgumentException(" V- " + V + " is illegal!");
            }
            adj = new int[V][V];
            E = scanner.nextInt();
            if (E < 0) {
                throw new IllegalArgumentException("E- " + E + "is illegal!");
            }

            // 依次获取每行的数据
            for (int i = 0; i < E; i++) {
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();

                // 校验自环边和平行边
                if (a == b) {
                    throw new IllegalArgumentException("发现自环边");
                }
                if (adj[a][b] == 1) {
                    throw new IllegalArgumentException("发现平行边");
                }

                validateVertex(b);
                adj[a][b] = 1;// 代表 顶点a 和顶点b 是相邻的。
                adj[b][a] = 1;
            }

        } catch (IOException E) {
            E.fillInStackTrace();
        }
    }

    // 校验图的顶点是否合法
    private void validateVertex(int v) {
        if (v < 0 || v >= V) {
            throw new IllegalArgumentException("v " + v + " is illegal!");
        }
    }

    // 获取图的顶点的数量
    public int V() {
        return V;
    }

    // 获取图的边的数量
    public int E() {
        return E;
    }

    // 判断两点之间是否相邻
    public boolean hasEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        // 当adj[v][w]==1 说明顶点v 和顶点w 相邻
        return adj[v][w] == 1;
    }

    //获取图中给定的顶点相邻的顶点
    public ArrayList<Integer> adj(int v) {
        validateVertex(v);
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            if (adj[v][i] == 1) {
                res.add(i);
            }
        }
        return res;
    }

    // 求一个顶点的度  度就是顶点的边
    public int degree(int v) {
        return adj(v).size();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V =%d, E=%d\n", V, E));
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                sb.append(String.format("%d ", adj[i][j]));
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        AdjacentMatrix adjacentMatrix = new AdjacentMatrix("graph_base_expression.txt");
        System.out.println(adjacentMatrix);
    }
}
